package com.tantou.java.structandalgorithm.tree;

import java.util.LinkedList;

public class BinaryTree {

    public static void main(String[] args) {

    }

    public static BTNode search(BTNode node, int target) {
        BTNode cur = node;
        while (cur != null) {
            if (cur.value == target) {
                return cur;
            } else if (cur.value < target) {
                //目标值比节点大，查找右子树
                cur = node.right;
            } else {
                cur = node.left;
            }
        }
        return null;
    }

    /**
     * 插入一个节点到二叉树中
     */
    public static void insert(BTNode tree, int target) {
        BTNode cur = tree;
        while (cur != null) {
            if (cur.value < target) {
                //如果比节点大，则看有没有右节点
                if (cur.right == null) {
                    cur.right = new BTNode(target);
                    return;
                } else {
                    //如果右节点存在，则继续遍历右子树
                    cur = cur.right;
                }
            } else {
                if (cur.left == null) {
                    cur.left = new BTNode(target);
                    return;
                } else {
                    cur = cur.left;
                }
            }
        }
    }


    public static void remove(BTNode tree, int target) {
        BTNode p = tree;
        BTNode pp = null;//p的父节点

        while (p != null & p.value != target) {
            //要删除的节点不是当前节点
            pp = p;
            if (p.value < target) {
                p = p.right;
            } else {
                p = p.left;
            }
        }

        if (p == null) {
            //没有找到该节点
            return;
        }

        //该节点有2个子节点
        if (p.left != null && p.right != null) {
            BTNode minP = p.right;
            BTNode minPP = p;
            //找到右子树的最小值，即最小左子树
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            //将最小节点赋给p
            p.value = minP.value;
            //删除minP
            p = minP;
            pp = minPP;
        }

        //只有一个子节点的情况
        BTNode child;
        if (p.left != null) {
            child = p.left;
        } else if (p.right != null) {
            child = p.right;
        } else {
            child = null;
        }
        if (pp == null) {
            tree = child;
        } else if (pp.left == p) {
            //如果父节点的左子树是p，则将上面找到的节点的做子节点向上赋值
            pp.left = child;
        } else {
            pp.right = child;
        }
    }
}


